import java.util.ArrayList;
import java.util.List;

/**
 * 
 * @author Owner Kevin Curtin, Ryan Diaz
 * 
 * This class implements a red-black tree which 
 * will be controlled by RedBlackGUI
 */
public class RedBlackTree<T extends Comparable<T>>{  
	Node<T> root; 

	static final int BLACK = 1;
	static final int RED = 0;
	private static final int NEGATIVE_RED = -1;
	private static final int DOUBLE_BLACK = 2;

	/**
		Constructs a new tree.
	 */
	public RedBlackTree(){  
		root = null;
	}
   
	/**
      	Inserts a new node into the tree.
      	@param obj the object to insert
	 */
	public void add(T obj){  
		Node<T> newNode = new Node<T>();
		newNode.data = obj;
		newNode.left = null;
		newNode.right = null;
		if (root == null) { root = newNode; }
		else { root.addNode(newNode); }
		fixAfterAdd(newNode);
		checkEachNode(root);
	}

	/**
      	Tries to find an object in the tree.
      	@param obj the object to find
      	@return true if the object is contained in the tree
	 */
	public boolean find(T obj){
		Node<T> current = root;
		while (current != null){
			int d = current.data.compareTo(obj);
			if (d == 0) return true;
			else if (d > 0) current = current.left;
			else current = current.right;
		}
		return false;
	}
	
	public void clear() {
		root = null;
	}
   
	/**
      	Tries to remove an object from the tree. Does nothing
      	if the object is not contained in the tree.
      	@param obj the object to remove
	 */
	public void remove(T obj){
		// Find node to be removed

		Node<T> toBeRemoved = root;
		boolean found = false;
		while (!found && toBeRemoved != null){
			int d = toBeRemoved.data.compareTo(obj);
			if (d == 0) { found = true; }
			else{
				if (d > 0) { toBeRemoved = toBeRemoved.left; }
            else { toBeRemoved = toBeRemoved.right; }
			}
		}

		if (!found) { 
			checkEachNode(root);
			return; 
		}

		// toBeRemoved contains obj

		// If one of the children is empty, use the other

		if (toBeRemoved.left == null || toBeRemoved.right == null){
			Node<T> newChild;
			if (toBeRemoved.left == null) { newChild = toBeRemoved.right; }
			else { newChild = toBeRemoved.left; }

			fixBeforeRemove(toBeRemoved); 
         
			if (toBeRemoved.parent == null) { root = newChild; } // Found in root
			else { toBeRemoved.replaceWith(newChild); }
			checkEachNode(root);
			return;
		}
      
		// Neither subtree is empty

		// Find smallest element of the right subtree

		Node<T> smallest = toBeRemoved.right;
		while (smallest.left != null){
			smallest = smallest.left;
		}

		// smallest contains smallest child in right subtree
         
		// Move contents, unlink child

		toBeRemoved.data = smallest.data;
		fixBeforeRemove(smallest);
		smallest.replaceWith(smallest.right);
	}
   
	/**
      	Visits all nodes of this tree in order.
      	@param v the visitor to apply at each node
	 */
	public void inOrderVisit(Visitor v){
		inOrderVisit(root, v);
	}
	
	public static interface Visitor{
		/**
            This method is called at each node.
         	@param n the visited node
		 */
		void visit(Node n);
	}
	public void checkEachNode(Node n) {
		if (n == null) return;
		checkEachNode(n.left);
		checkNode(n);
		checkEachNode(n.right);
	}
	public void checkNode(Node<T> n) {
		if (root == null) return;
		if (n == null) return;
		if (n.left != null && n.right != null) {
			if (n.left.color == BLACK && n.right.color == BLACK && n != root) {
				n.color = RED;
			}
		}
		
	}
   
	private static void inOrderVisit(Node n, Visitor v){
		if (n == null) return;
		inOrderVisit(n.left, v);
		v.visit(n);
		inOrderVisit(n.right, v);
	}
   
	/**
      A node of a red-black tree stores a data item and references
      of the child nodes to the left and to the right. The color
      is the "cost" of passing the node; 1 for black or 0 for red.
      Temporarily, it may be set to 2 or -1. 
	 */

	/**
      Restores the tree to a red-black tree after a node has been added.
      @param newNode the node that has been added
	 */
	private void fixAfterAdd(Node<T> newNode){
		if (newNode.parent == null){ 
			newNode.color = BLACK; 
		}
		else{
			newNode.color = RED;
         	if (newNode.parent.color == RED) { fixDoubleRed(newNode); }
     	}
	}

	/** 	
     	Fixes the tree so that it is a red-black tree after a node has been removed.
     	@param removed the node that is to be removed
	 */
	private void fixBeforeRemove(Node<T> removed){
		if (removed.color == RED) { return; }

		if (removed.left != null || removed.right != null){ // It is not a leaf
			// Color the child black
			if (removed.left == null) { removed.right.color = BLACK; }
			else { removed.left.color = BLACK; }
		}	   
		else { bubbleUp(removed.parent); }
	}
   
	/**
      	Move a charge from two children of a parent
      	@param parent a node with two children, or null (in which case nothing is done)
	 */
	private void bubbleUp(Node<T> parent){
		if (parent == null) { return; }
		parent.color++;
		parent.left.color--;
		parent.right.color--;
	   
		Node<T> child = parent.left;
		if (child.color == NEGATIVE_RED) { fixNegativeRed(child); return; }
		else if (child.color == RED){
			if (child.left != null && child.left.color == RED){ 
				fixDoubleRed(child.left); 
				return; 
			}
			if (child.right != null && child.right.color == RED) { 
				fixDoubleRed(child.right); return; 
			}
		}
   
		child = parent.right;
		if (child.color == NEGATIVE_RED) { fixNegativeRed(child); return; }
		else if (child.color == RED){
			if (child.left != null && child.left.color == RED){ 
				fixDoubleRed(child.left); 
				return; 
			}
			if (child.right != null && child.right.color == RED){ 
				fixDoubleRed(child.right); 
				return; 
			}	
		}
	  
		if (parent.color == DOUBLE_BLACK){ 
			if (parent.parent == null) { parent.color = BLACK; }
			else { bubbleUp(parent.parent); }
		}
	}
   
   
	/**
      	Fixes a "double red" violation.
      	@param child the child with a red parent
	 */
	private void fixDoubleRed(Node<T> child){
		Node<T> parent = child.parent;      
		Node<T> grandParent = parent.parent;
		if (grandParent == null) { parent.color = BLACK; return; }
		Node<T> n1, n2, n3, t1, t2, t3, t4;
		if (parent == grandParent.left){
			n3 = grandParent; t4 = grandParent.right;
			if (child == parent.left){
				n1 = child; n2 = parent;
				t1 = child.left; t2 = child.right; t3 = parent.right;
			}
			else{
				n1 = parent; n2 = child;
				t1 = parent.left; t2 = child.left; t3 = child.right; 
			}
		}
		else{
			n1 = grandParent; t1 = grandParent.left;
			if (child == parent.left){
				n2 = child; n3 = parent;
				t2 = child.left; t3 = child.right; t4 = parent.right;
			}
			else{
				n2 = parent; n3 = child;
				t2 = parent.left; t3 = child.left; t4 = child.right; 
			}         
		}
      
		if (grandParent == root){
			root = n2;
			n2.parent = null;
     	}
		else{
			grandParent.replaceWith(n2);
		}
      
		n1.setLeftChild(t1);
	    n1.setRightChild(t2);
	    n2.setLeftChild(n1); 
	    n2.setRightChild(n3);
	    n3.setLeftChild(t3);
	    n3.setRightChild(t4);		
	    n2.color = grandParent.color - 1; 
	    n1.color = BLACK;
	    n3.color = BLACK;

	    if (n2 == root){
	    	root.color = BLACK;
	    }
	    else if (n2.color == RED && n2.parent.color == RED){
	    	fixDoubleRed(n2);
	    }
	}
   
	/**
      	Fixes a "negative red" violation.
      	@param negRed the negative red node
	 */
	private void fixNegativeRed(Node<T> negRed){	
		Node<T> n1, n2, n3, n4, t1, t2, t3, child;
		Node<T> parent = negRed.parent;
		if (parent.left == negRed){
			n1 = negRed.left;
			n2 = negRed;
			n3 = negRed.right;
			n4 = parent;
			t1 = n3.left;
			t2 = n3.right;
			t3 = n4.right;
			n1.color = RED;
         	n2.color = BLACK;
         	n4.color = BLACK;
         	n2.setRightChild(t1);
         	T temp = n4.data; n4.data = n3.data; n3.data = temp;
         	n3.setLeftChild(t2);
         	n3.setRightChild(t3);
         	n4.setRightChild(n3);
         	child = n1;
		}
		else{
			n4 = negRed.right;
			n3 = negRed;
			n2 = negRed.left;
			n1 = parent;
			t3 = n2.right;
			t2 = n2.left;
			t1 = n1.left;
			n4.color = RED;
			n3.color = BLACK;
			n1.color = BLACK;
			n3.setLeftChild(t3);
			T temp = n1.data; n1.data = n2.data; n2.data = temp;
			n2.setRightChild(t2);
			n2.setLeftChild(t1);
			n1.setLeftChild(n2);
			child = n4;
		}
	   
		if (child.left != null && child.left.color == RED){ 
			fixDoubleRed(child.left); 
			return; 
		}
		if (child.right != null && child.right.color == RED){ 
			fixDoubleRed(child.right);  
		}
	}
  
}



